Single row facility layout problem using a permutation-based genetic algorithm
Identifieur interne : 002388 ( Main/Exploration ); précédent : 002387; suivant : 002389Single row facility layout problem using a permutation-based genetic algorithm
Auteurs : José Rui Figueira [France] ; Dilip Datta [Portugal] ; André R. S Amaral [Portugal]Source :
- European Journal of Operational Research [ 0377-2217 ] ; 2011-04-13.
English descriptors
Abstract
In this paper, a permutation-based genetic algorithm (GA) is applied to the NP-hard problem of arranging a number of facilities on a line with minimum cost, known as the single row facility layout problem (SRFLP). The GA individuals are obtained by using some rule-based as well as random permutations of the facilities, which are then improved towards the optimum by means of specially designed crossover and mutation operators. Such schemes led the GA to handle the SRFLP as an unconstrained optimization problem. In the computational experiments carried out with large-size instances of sizes from 60 to 80, available in the literature, the proposed GA improved several previously known best solutions.
Url:
DOI: 10.1016/j.ejor.2011.03.034
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream Hal, to step Corpus: 004593
- to stream Hal, to step Curation: 004593
- to stream Hal, to step Checkpoint: 001E71
- to stream Main, to step Merge: 002436
- to stream Main, to step Curation: 002388
Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">Single row facility layout problem using a permutation-based genetic algorithm</title><author><name sortKey="Figueira, Jose Rui" sort="Figueira, Jose Rui" uniqKey="Figueira J" first="José Rui" last="Figueira">José Rui Figueira</name><affiliation wicri:level="1"><hal:affiliation type="researchteam" xml:id="struct-44715" status="VALID"><orgName>Operations research for Complex HybrId Decision Sytems</orgName><orgName type="acronym">ORCHIDS</orgName><desc><address><country key="FR"></country></address><ref type="url">http://www.loria.fr/la-recherche/equipes/orchids</ref></desc><listRelation><relation active="#struct-423085" type="direct"></relation><relation active="#struct-206040" type="indirect"></relation><relation active="#struct-300009" type="indirect"></relation><relation active="#struct-413289" type="indirect"></relation><relation name="UMR7503" active="#struct-441569" type="indirect"></relation></listRelation><tutelles><tutelle active="#struct-423085" type="direct"><org type="department" xml:id="struct-423085" status="VALID"><orgName>Department of Networks, Systems and Services</orgName><orgName type="acronym">LORIA - NSS</orgName><desc><address><country key="FR"></country></address><ref type="url">http://www.loria.fr/la-recherche-en/departements/networks-systems-and-services</ref></desc><listRelation><relation active="#struct-206040" type="direct"></relation><relation active="#struct-300009" type="indirect"></relation><relation active="#struct-413289" type="indirect"></relation><relation name="UMR7503" active="#struct-441569" type="indirect"></relation></listRelation></org></tutelle><tutelle active="#struct-206040" type="indirect"><org type="laboratory" xml:id="struct-206040" status="VALID"><idno type="IdRef">067077927</idno><idno type="RNSR">198912571S</idno><idno type="IdUnivLorraine">[UL]RSI--</idno><orgName>Laboratoire Lorrain de Recherche en Informatique et ses Applications</orgName><orgName type="acronym">LORIA</orgName><date type="start">2012-01-01</date><desc><address><addrLine>Campus Scientifique BP 239 54506 Vandoeuvre-lès-Nancy Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.loria.fr</ref></desc><listRelation><relation active="#struct-300009" type="direct"></relation><relation active="#struct-413289" type="direct"></relation><relation name="UMR7503" active="#struct-441569" type="direct"></relation></listRelation></org></tutelle><tutelle active="#struct-300009" type="indirect"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName><orgName type="acronym">Inria</orgName><desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/en/</ref></desc></org></tutelle><tutelle active="#struct-413289" type="indirect"><org type="institution" xml:id="struct-413289" status="VALID"><idno type="IdRef">157040569</idno><idno type="IdUnivLorraine">[UL]100--</idno><orgName>Université de Lorraine</orgName><orgName type="acronym">UL</orgName><date type="start">2012-01-01</date><desc><address><addrLine>34 cours Léopold - CS 25233 - 54052 Nancy cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.univ-lorraine.fr/</ref></desc></org></tutelle><tutelle name="UMR7503" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="IdRef">02636817X</idno><idno type="ISNI">0000000122597504</idno><orgName>Centre National de la Recherche Scientifique</orgName><orgName type="acronym">CNRS</orgName><date type="start">1939-10-19</date><desc><address><country key="FR"></country></address><ref type="url">http://www.cnrs.fr/</ref></desc></org></tutelle></tutelles></hal:affiliation><country>France</country><placeName><settlement type="city">Nancy</settlement><settlement type="city">Metz</settlement><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region></placeName><orgName type="university">Université de Lorraine</orgName></affiliation></author><author><name sortKey="Datta, Dilip" sort="Datta, Dilip" uniqKey="Datta D" first="Dilip" last="Datta">Dilip Datta</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-46039" status="VALID"><orgName>Instituto Superior Técnico - Technical University of Lisbon</orgName><orgName type="acronym">IST</orgName><desc><address><addrLine>R. Alves Redol, n.9, 1000–129 Lisboa</addrLine><country key="PT"></country></address><ref type="url">http://www.ist.utl.pt/</ref></desc><listRelation><relation active="#struct-368878" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-368878" type="direct"><org type="institution" xml:id="struct-368878" status="INCOMING"><orgName>Technical University of Lisbon</orgName><desc><address><country key="FR"></country></address></desc></org></tutelle></tutelles></hal:affiliation><country>Portugal</country></affiliation></author><author><name sortKey="Amaral, Andre R S" sort="Amaral, Andre R S" uniqKey="Amaral A" first="André R. S" last="Amaral">André R. S Amaral</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-46039" status="VALID"><orgName>Instituto Superior Técnico - Technical University of Lisbon</orgName><orgName type="acronym">IST</orgName><desc><address><addrLine>R. Alves Redol, n.9, 1000–129 Lisboa</addrLine><country key="PT"></country></address><ref type="url">http://www.ist.utl.pt/</ref></desc><listRelation><relation active="#struct-368878" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-368878" type="direct"><org type="institution" xml:id="struct-368878" status="INCOMING"><orgName>Technical University of Lisbon</orgName><desc><address><country key="FR"></country></address></desc></org></tutelle></tutelles></hal:affiliation><country>Portugal</country></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">HAL</idno><idno type="RBID">Hal:inria-00602168</idno><idno type="halId">inria-00602168</idno><idno type="halUri">https://hal.inria.fr/inria-00602168</idno><idno type="url">https://hal.inria.fr/inria-00602168</idno><idno type="doi">10.1016/j.ejor.2011.03.034</idno><date when="2011-04-13">2011-04-13</date><idno type="wicri:Area/Hal/Corpus">004593</idno><idno type="wicri:Area/Hal/Curation">004593</idno><idno type="wicri:Area/Hal/Checkpoint">001E71</idno><idno type="wicri:explorRef" wicri:stream="Hal" wicri:step="Checkpoint">001E71</idno><idno type="wicri:doubleKey">0377-2217:2011:Figueira J:single:row:facility</idno><idno type="wicri:Area/Main/Merge">002436</idno><idno type="wicri:Area/Main/Curation">002388</idno><idno type="wicri:Area/Main/Exploration">002388</idno></publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en">Single row facility layout problem using a permutation-based genetic algorithm</title><author><name sortKey="Figueira, Jose Rui" sort="Figueira, Jose Rui" uniqKey="Figueira J" first="José Rui" last="Figueira">José Rui Figueira</name><affiliation wicri:level="1"><hal:affiliation type="researchteam" xml:id="struct-44715" status="VALID"><orgName>Operations research for Complex HybrId Decision Sytems</orgName><orgName type="acronym">ORCHIDS</orgName><desc><address><country key="FR"></country></address><ref type="url">http://www.loria.fr/la-recherche/equipes/orchids</ref></desc><listRelation><relation active="#struct-423085" type="direct"></relation><relation active="#struct-206040" type="indirect"></relation><relation active="#struct-300009" type="indirect"></relation><relation active="#struct-413289" type="indirect"></relation><relation name="UMR7503" active="#struct-441569" type="indirect"></relation></listRelation><tutelles><tutelle active="#struct-423085" type="direct"><org type="department" xml:id="struct-423085" status="VALID"><orgName>Department of Networks, Systems and Services</orgName><orgName type="acronym">LORIA - NSS</orgName><desc><address><country key="FR"></country></address><ref type="url">http://www.loria.fr/la-recherche-en/departements/networks-systems-and-services</ref></desc><listRelation><relation active="#struct-206040" type="direct"></relation><relation active="#struct-300009" type="indirect"></relation><relation active="#struct-413289" type="indirect"></relation><relation name="UMR7503" active="#struct-441569" type="indirect"></relation></listRelation></org></tutelle><tutelle active="#struct-206040" type="indirect"><org type="laboratory" xml:id="struct-206040" status="VALID"><idno type="IdRef">067077927</idno><idno type="RNSR">198912571S</idno><idno type="IdUnivLorraine">[UL]RSI--</idno><orgName>Laboratoire Lorrain de Recherche en Informatique et ses Applications</orgName><orgName type="acronym">LORIA</orgName><date type="start">2012-01-01</date><desc><address><addrLine>Campus Scientifique BP 239 54506 Vandoeuvre-lès-Nancy Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.loria.fr</ref></desc><listRelation><relation active="#struct-300009" type="direct"></relation><relation active="#struct-413289" type="direct"></relation><relation name="UMR7503" active="#struct-441569" type="direct"></relation></listRelation></org></tutelle><tutelle active="#struct-300009" type="indirect"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName><orgName type="acronym">Inria</orgName><desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/en/</ref></desc></org></tutelle><tutelle active="#struct-413289" type="indirect"><org type="institution" xml:id="struct-413289" status="VALID"><idno type="IdRef">157040569</idno><idno type="IdUnivLorraine">[UL]100--</idno><orgName>Université de Lorraine</orgName><orgName type="acronym">UL</orgName><date type="start">2012-01-01</date><desc><address><addrLine>34 cours Léopold - CS 25233 - 54052 Nancy cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.univ-lorraine.fr/</ref></desc></org></tutelle><tutelle name="UMR7503" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="IdRef">02636817X</idno><idno type="ISNI">0000000122597504</idno><orgName>Centre National de la Recherche Scientifique</orgName><orgName type="acronym">CNRS</orgName><date type="start">1939-10-19</date><desc><address><country key="FR"></country></address><ref type="url">http://www.cnrs.fr/</ref></desc></org></tutelle></tutelles></hal:affiliation><country>France</country><placeName><settlement type="city">Nancy</settlement><settlement type="city">Metz</settlement><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region></placeName><orgName type="university">Université de Lorraine</orgName></affiliation></author><author><name sortKey="Datta, Dilip" sort="Datta, Dilip" uniqKey="Datta D" first="Dilip" last="Datta">Dilip Datta</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-46039" status="VALID"><orgName>Instituto Superior Técnico - Technical University of Lisbon</orgName><orgName type="acronym">IST</orgName><desc><address><addrLine>R. Alves Redol, n.9, 1000–129 Lisboa</addrLine><country key="PT"></country></address><ref type="url">http://www.ist.utl.pt/</ref></desc><listRelation><relation active="#struct-368878" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-368878" type="direct"><org type="institution" xml:id="struct-368878" status="INCOMING"><orgName>Technical University of Lisbon</orgName><desc><address><country key="FR"></country></address></desc></org></tutelle></tutelles></hal:affiliation><country>Portugal</country></affiliation></author><author><name sortKey="Amaral, Andre R S" sort="Amaral, Andre R S" uniqKey="Amaral A" first="André R. S" last="Amaral">André R. S Amaral</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-46039" status="VALID"><orgName>Instituto Superior Técnico - Technical University of Lisbon</orgName><orgName type="acronym">IST</orgName><desc><address><addrLine>R. Alves Redol, n.9, 1000–129 Lisboa</addrLine><country key="PT"></country></address><ref type="url">http://www.ist.utl.pt/</ref></desc><listRelation><relation active="#struct-368878" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-368878" type="direct"><org type="institution" xml:id="struct-368878" status="INCOMING"><orgName>Technical University of Lisbon</orgName><desc><address><country key="FR"></country></address></desc></org></tutelle></tutelles></hal:affiliation><country>Portugal</country></affiliation></author></analytic><idno type="DOI">10.1016/j.ejor.2011.03.034</idno><series><title level="j">European Journal of Operational Research</title><idno type="ISSN">0377-2217</idno><imprint><date type="datePub">2011-04-13</date></imprint></series></biblStruct></sourceDesc></fileDesc><profileDesc><textClass><keywords scheme="mix" xml:lang="en"><term>Single row facility layout problem Genetic algorithm Combinatorial optimization</term></keywords></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">In this paper, a permutation-based genetic algorithm (GA) is applied to the NP-hard problem of arranging a number of facilities on a line with minimum cost, known as the single row facility layout problem (SRFLP). The GA individuals are obtained by using some rule-based as well as random permutations of the facilities, which are then improved towards the optimum by means of specially designed crossover and mutation operators. Such schemes led the GA to handle the SRFLP as an unconstrained optimization problem. In the computational experiments carried out with large-size instances of sizes from 60 to 80, available in the literature, the proposed GA improved several previously known best solutions.</div></front></TEI><affiliations><list><country><li>France</li><li>Portugal</li></country><region><li>Grand Est</li><li>Lorraine (région)</li></region><settlement><li>Metz</li><li>Nancy</li></settlement><orgName><li>Université de Lorraine</li></orgName></list><tree><country name="France"><region name="Grand Est"><name sortKey="Figueira, Jose Rui" sort="Figueira, Jose Rui" uniqKey="Figueira J" first="José Rui" last="Figueira">José Rui Figueira</name></region></country><country name="Portugal"><noRegion><name sortKey="Datta, Dilip" sort="Datta, Dilip" uniqKey="Datta D" first="Dilip" last="Datta">Dilip Datta</name></noRegion><name sortKey="Amaral, Andre R S" sort="Amaral, Andre R S" uniqKey="Amaral A" first="André R. S" last="Amaral">André R. S Amaral</name></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 002388 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 002388 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= Main
|étape= Exploration
|type= RBID
|clé= Hal:inria-00602168
|texte= Single row facility layout problem using a permutation-based genetic algorithm
}}
| This area was generated with Dilib version V0.6.33. |  |